OI Review

JOI

2023

P3 Maze

01-BFS. 이미 뚫려 있는 칸이라면 비용 0으로 이동하고 뚫려 있지 않은 칸이라면 현재 위치 중심으로 정사각형 영역에 벽의 존재 유무와 무관하게 비용 1으로 이동한다. 한번 데큐에 들어간 정점들을 다시 넣지 않도록 하여 시간을 줄여야 하는데, 구간에 켜져 있는 칸 모두 돌며 삭제 연산을 해야 하니 set이나 union find 자료구조로 해결한다.

2022

P3 Let’s Win the Election

최적해는 collaborator을 얻을 지역을 우선 순회하며 \(i\)명 얻은 후, 남은 지역들 중 \(A_i\)가 가장 작은 것 \(K-i\)개를 먹는 형태이다. 즉, \(K\)중 몇개를 \(B\), 몇개를 \(A\)로 칠해 먼저 \(B\)들을 증가 순서대로 먹은 후 남은 지역들 중 가장 작은 \(A_i\)들을 골라 담으면 된다. 구체적으로는, 특정 상수 \(X\), \(Y\)에 대해서 \(A \le X\)이거나 \(B \le Y\)인 것들을 모두 먹게 된다. 먹을 \(B\) 지역의 개수를 고정해놓고 생각하자. \(B\)에 대해서 정렬해놓고 생각하고, 앞에서부터 하나씩 \(B\)로 먹을지, \(A\)로 먹을지 결정하며 \(dp[i][j] :=\) \(i\)까지 봤고, 지금까지 B는 \(j\)로 먹었을 떄의 최소 비용의 합을 계산한다. \(B\)를 정한 만큼 다 먹으면 남은 것들 중 먹어야 하는만큼 작은거부터 골라서 먹어주면 된다. 먹을 지역의 개수를 고정해놓았기 떄문에 dp를 하는 과정에서 위 식을 계산할 수 있다. 변수 고정과 dp에 \(O(N^3)\)의 시간이 걸린다.

P4 Railway Trip 2

각 정점에서 시작하면 한 번의 이동으로 어떤 영역까지 이동할 수 있는지 생각하자. 이는 현재 내 위치를 커버할 수 있는 열차들 중 최댓값과 최솟값 쿼리로 스위핑하면서 구할 수 있다. 이제, 문제는 각 정점에서 1의 가중치로 이동할 수 있는 구간이 주어질 때, \(s\)에서 \(e\)까지 가는 최단경로 쿼리에 대해 답해야 한다. 가중치 \(k\)로 이동할 수 있는 정점들은 항상 구간을 이루고, 이 구간들은 \(k\)가 증가하면 할수록 확장되는 형태이다. 이를 sparse table을 이용하여 관리할건데, 현재 위치에서 \(2^{i+1}\)번의 이동으로 도착할 수 있는 구간은 \(2^i\)번의 이동으로 도착할 수 있는 구간들의 값 중 min, max의 형태이니, range min / max query를 sparse table의 각 층에 대하여 날려서 구할 수 있다.

P5 Sandcastle 2

핵심 관찰은 전체 직사각형이 올바른 직사각형일 필요충분 조건은, 각 정점에서 인접한 칸들 중 자신보다 작은 것 중 최대인 칸으로 간선을 이었을 떄, 모든 칸의 \(outdegree=1\), \(indegree=1\)이며, 딱 한 정점만 \(outdegree \ne 1\), 딱 한 정점만 \(indegree \ne 1\)이라는 것이다. 또한, \(HW \le N\)인 상황에서 \(min(H, W) HW \le N \sqrt{N}\)이라는 점을 생각하자. WLOG \(H \le W\)라면, \(1 \le i \le j \le H\)를 모두 고정해보며, \(O(W)\)에 올바른 직사각형의 개수를 세주면 되는데, 결국 중요한건 \(indegree \ne 1\), \(outdegree \ne 1\)인 칸의 개수라는 것에 집중하자. 부분직사각형을 잡았을 때, 테두리에서 멀리 떨어져 있는 칸들의 입장에서는 부분직사각형과 무관하게 indegree, outdegree가 일정하다는 점을 생각하면 가능한 모든 경우가 \(3^4\)가지 정도밖에 없고, 이를 미리 전처리해놓으면, 단순 누적합 작업 등으로 답을 계산할 수 있다.

2020

P4 Olympic Bus

간선 \((u, v)\)를 뒤집는다고 생각했을 때의 답은 우선 그래프에서 \((u, v)\)를 삭제한 후, \(1 \rightarrow N\)은 \(min(dist(1, v)+w+dist(u, N), dist(1, N))\)이고, 비슷하게 \(N \rightarrow 1\)도 구할 수 있다. 중요한 것은 간선을 그래프에서 삭제해야한다는 것인데, 다익스트라를 돌리는 과정에서 최단경로를 갱신하는데 사용한 간선을 각 정점에 대해서 하나씩 골라서 다익스트라 트리를 만들자. 간선 \((u, v)\)가 다익스트라 트리에 사용되지 않는다면, 이 간선이 없어도 최단경로는 바뀌지 않으니, 문제가 없다. 다익스트라 트리에 사용된다면, 그런 간선의 수는 \(O(N)\)개밖에 없으니, 다익스트라를 다시 돌려줘도 \(O(NM\log N)\)밖에 걸리지 않는다.

P5 Fire

\(S_i\)로 구성된 히스토그램을 그리고, 각 히스토그램을 오른쪽으로 확장한 형태의 직사각형을 생각하자. 또한, 쿼리 \((t, l, r)\)은 누적합을 생각하면 \((t, x)\)로 쪼개어 생각할 수 있다. 각 직사각형의 형태는 \((l, r, k)\)의 형태로, 직사각형의 높이는 \(k\), 왼쪽 변은 \(x=l\), 오른쪽 변은 \(x=min(r, l+t)\)일 때, \((t, x)\) 쿼리에 대해서 \(x\) 이하의 영역의 직사각형의 넓이의 합을 구하면 된다. \((x, t)\) 좌표평면에 각 직사각형의 정보를 표현하면 결국 다음 문제를 풀어야 함을 알 수 있다. 각 직사각형은 점 \((x, y)\)를 기준으로 위쪽으로 \(y\)축에 평행인 반직선과 \(y=x\)에 평행인 반직선으로 구성된 영역의 점들에 모두 \(k\)를 더하는 형태이고, 각 쿼리는 점 \((x, y)\)를 기준으로 왼쪽으로 이동하며 만나는 모든 값들의 합이다. 직사각형 업데이트 \((x, y)\)와 쿼리 \((x', y')\)을 기준으로 생각하면 \(x-y\), \(x'-y'\)의 대소관계에 따라 경우를 나누어 생각하면, 두 경우에 따라 \(x\)와 \(y\)중 한 변수를 무시해도 됨을 알 수 있다. 따라서, \(x-y\)로 모든 업데이트와 쿼리들을 정렬한 후, 각 경우에 대하여 \(x\)나 \(y\)축에 사영시켜 fenwick tree를 이용하여 계산할 수 있다.

2019

P4 Coin Collecting

우선, 크기 \(2N\)의 직사각형 영역 밖의 점들에 대해서는 가장 가까운 직사각형 안의 점으로 이동시키고 생각해도 된다. 이제, 문제는 \(2N\)의 직사각형 영역에 동전들이 총 \(2N\)개 놓여 있을 때, 이를 적당히 이동시켜 직사각형의 각 칸에 동전이 하나씩 놓여 있도록 하는 최소 이동이다. 이는 쉽게 MCMF로 모델링할 수 있고, 따라서 그리디하게 동전을 자기가 들어갈 수 있는 가장 가까운 구멍으로 매칭시켜도 문제가 발생하지 않는다. 이를 쉽게 구현하면, 첫 번째 열부터 시작해 스위핑하며 동전이 남으면 오른쪽으로 한 칸씩 밀어주고, 부족하다면 꼭 필요한 만큼만 미리 대출을 받아 오른쪽에서 받아온다고 생각하고 계산을 해줘도 된다.

P5 Unique Cities

https://arnold518.tistory.com/78

2018

P3 Dango Maker

서로 영향을 줄 수 있는 dango들은 가로/세로 여부가 달라야 하고, 구체적으로는 "RGW" 중 각 R, G, W들이 같은 대각선 위에 있어야만 한다. 이 관찰로부터 만들 수 있는 모든 dango들을 만들어 놓고, 속해 있는 대각선에 따라 dango들을 묶어 줄 수 있다. 이제 각 집합에 대해서는 독립적으로 문제를 풀면 되고, 같은 집합에 해당하는 dango들에 대해서는 마지막 dango의 선택 여부만 기억하면 되니, \(O(N)\)에 dp를 통해 구할 수 있다.